package sword.offer;

import sword.offer.common.Node;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一棵二叉搜索树，请找出其中第k大的节点。
 * 链接 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FiftyFour {
    /**
     * 最直接简单的思路： <br />
     * 中序遍历，将结点放入到一个数组中，然后直接返回数组的倒数第k个元素即可
     * */
    class Solution {
        private List<Integer> values = new ArrayList<>();
        public int kthLargest(Node root, int k) {
            dfs(root);
            return values.get(values.size()-k);
        }

        public void dfs(Node root){
            if(root == null) { return ; }

            dfs(root.left);
            values.add(root.val);
            dfs(root.right);
        }
    }

    /**
     * 我们使用中序遍历，第一次回溯访问到的是第1小的值，第二次回溯是第2小的值
     * 在应用到第k大的值上面，我们需要将二叉搜索树的左右分支换过来遍历。
     * 即，我们还是使用中序遍历，只不过我们先遍历右子树 再访问中间结点 最后才遍历左子树。
     * */
    class Solution1 {
        private int count, ans;
        public int kthLargest(Node root, int k) {
            dfs(root ,k);
            return ans;
        }

        public void dfs(Node root, int k){
            if(root == null) { return; }
            dfs(root.right, k);
            count++;
            if(count == k){
                ans = root.val;
            }
            dfs(root.left, k);
        }
    }
}
